package com.bowlong.astar.kjava;

/**  
 * A*算法原理  
 * 在计算机中我们将地图表现为单元格，分可走单元格和不可走单元格。  
 * 如果用穷搜找最短路径当然是可以实现，但代价却很大。  
 * 于是我们必须要让计算机“有选择地走”。  
 * 若以当前单元格为起点（称为父单元格，它的周围有八个方向），下一步走哪呢？  
 * 这时就得给下一步的单元格（称为子单元格）进行“估价”。  
 * “估价”可用估价函数来实现。  
 * 入门级的估价函数是这样的：  
 * 终点到目前点的估计代价＝终点至当前点的直线距离  
 * 于是下一步的代价可以这样算  
 * 代价＝起点到当前点的实际步数（通过一个变量累加可以直接得到）+ 终点到目前点的估计代价  
 * 然后把估价后的单元格放入“待考察表”  
 * 从待考察表中取代价最小的单元格作为起点，对它周围8个方向的单元格进行估价，然后把它放入“已考察表”。  
 * 若对一个单元格估价时，发现它已经在“待考察表”中则比较该单元格原先的估价和当前的估价，保留小的估价，并更新其父单元格属性。  
 * 不断重复以上过程，直到在“待考察表”中取出的单元格是终点单元格为止，若“待考察表为空”则表示找不到路径。  
 * 到达终点单元格后，通过其“父单元格”属性，一直找到起点，便构成一条路径。  
 */

/**  
 * <p>A* </p>  
 * <p>Description: MyTestProject</p>  
 * <p>Copyright: Copyright (c) 2008</p>  
 * <p>Company: </p>  
 * @author Coleman  
 * @version 1.0  
 */
import java.util.Vector;

@SuppressWarnings({ "unchecked", "rawtypes", "unused" })
public class AStar implements Runnable {
	private static final byte UP = 0;
	private static final byte DOWN = 1;
	private static final byte LEFT = 2;
	private static final byte RIGHT = 3;

	private static AStar as;
	private static Vector openList = new Vector();// 待检查列表
	private static Vector closeList = new Vector();// 已检查列表
	private static int pane[][];// 地图方格
	private static int go = 1;// 设置为pane中的通路值
	private static int obstacle = 9;// 障碍物的计算消耗
	private static int pos_begin[];// 出发位置
	private static int pos_end[];// 终点位置
	private static int nodeID = 0;// 标志当前处理的点在openlist中的位置

	private static volatile boolean isStoped = true;// 停止搜索或者搜索结束

	private static boolean isFinded = false;// 是否找到路径
	private static int path[][];// 找出的路径
	private static Node path_node;// 路径目标结点

	private static long cost_time = 0;// 寻路耗时

	private static boolean isChecked = false;// 是否检查
	public static int[][] check;// 所有待检查点 记录到数组中

	private AStar() {
		if (as == null)
			as = this;
	}

	private static AStar getInstance() {
		if (as == null)
			as = new AStar();
		return as;
	}

	public static long getTimeCost() {
		return cost_time;
	}

	public void run() {
		long begin_time = System.currentTimeMillis();
		Node begin_node = new Node(pos_begin[0], pos_begin[1],
				pane[pos_begin[0]][pos_begin[1]]);
		search(begin_node);
		long end_time = System.currentTimeMillis();
		cost_time = end_time - begin_time;
	}

	public static void initCheck(int check_length) {
		isChecked = true;
		check = new int[check_length][2];
	}

	public static void init(int Go, int Obstacle, int Pane[][],
			int Pos_begin[], int Pos_end[]) {
		go = Go;
		pane = Pane;
		pos_begin = Pos_begin;
		pos_end = Pos_end;

		isStoped = false;
		isFinded = false;

		cost_time = 0;

		new Thread(AStar.getInstance()).start();
	}

	public static int[][] getPath() {
		path = new int[path_node.depth][2];
		for (int i = path.length - 1; i >= 0; i--) {
			path[i][0] = path_node.getX();
			path[i][1] = path_node.getY();
			path_node = path_node.getFather();
		}
		free();
		return path;
	}

	public static boolean isPathFinded() {
		return isFinded;
	}

	public static boolean isSearchStopped() {
		return isStoped;
	}

	private static void free() {
		openList = null;
		closeList = null;
		pane = null;
		pos_begin = null;
		pos_end = null;
	}

	// /////////////////////AStar//////////////////////
	private int getG(Node n) {// 实际代价
		return n.G_value;
	}

	private int getH(Node n) {// 估计代价
		return Math.abs(n.getX() - pos_end[0])
				+ Math.abs(n.getY() - pos_end[1]);
	}

	private int getF(Node n) {// 总代价
		return (getG(n) + getH(n));
	}

	private boolean hasChild(Node n, int dir) {
		switch (dir) {
		case UP:// 上面有没有子结点
			if (n.getY() == 0)
				return false;
			if (pane[n.getY() - 1][n.getX()] == 1)
				return true;
			break;
		case DOWN:
			if (n.getY() == pane.length - 1)
				return false;
			if (pane[n.getY() + 1][n.getX()] == 1)
				return true;
			break;
		case LEFT:
			if (n.getX() == 0)
				return false;
			if (pane[n.getY()][n.getX() - 1] == 1)
				return true;
			break;
		case RIGHT:
			if (n.getX() == pane[0].length - 1)
				return false;
			if (pane[n.getY()][n.getX() + 1] == 1)
				return true;
			break;
		}
		return false;
	}

	private boolean inCloseList(int pos[]) {
		for (int i = 0; i < openList.size(); i++) {
			Node close_n = (Node) closeList.elementAt(i);
			if (close_n.getX() == pos[0] && close_n.getY() == pos[1]) {
				return true;
			}
		}
		return false;
	}

	private boolean isExisted(Node n) {
		boolean b = false;
		for (int i = 0; i < openList.size(); i++) {
			Node open_n = (Node) openList.elementAt(i);
			if (open_n.getX() == n.getX() && open_n.getY() == n.getY()) {
				if (open_n.F_value > n.F_value) {
					openList.setElementAt(n, i);
					n = open_n;
				}
				b = true;
			}
		}
		return b;
	}

	private void moveToOpenList(Node n) {
		if (!isExisted(n))
			openList.addElement(n);
	}

	private boolean isInCloseList(Node n) {
		for (int i = 0; i < closeList.size(); i++) {
			Node node = (Node) closeList.elementAt(i);
			if (node.getX() == n.getX() && node.getY() == n.getY()) {
				return true;
			}
		}
		return false;
	}

	private void addChild(Node n) {
		if (hasChild(n, UP) && n.father_dir != UP) {
			Node nChild_up = new Node(n.getX(), n.getY() - 1,
					pane[n.getY() - 1][n.getX()]);
			if (!isInCloseList(nChild_up)) {
				nChild_up.set(n, DOWN);
				moveToOpenList(nChild_up);
				if (isChecked) {
					for (int i = 0; i < check.length; i++) {
						if (check[i][0] == 0 && check[i][1] == 0) {
							check[i][0] = nChild_up.pos[0];
							check[i][1] = nChild_up.pos[1];
							break;
						}
					}
				}
			}
		}
		if (hasChild(n, DOWN) && n.father_dir != DOWN) {
			Node nChild_down = new Node(n.getX(), n.getY() + 1,
					pane[n.getY() + 1][n.getX()]);
			if (!isInCloseList(nChild_down)) {
				nChild_down.set(n, UP);
				moveToOpenList(nChild_down);
				if (isChecked) {
					for (int i = 0; i < check.length; i++) {
						if (check[i][0] == 0 && check[i][1] == 0) {
							check[i][0] = nChild_down.pos[0];
							check[i][1] = nChild_down.pos[1];
							break;
						}
					}
				}
			}
		}
		if (hasChild(n, LEFT) && n.father_dir != LEFT) {
			Node nChild_left = new Node(n.getX() - 1, n.getY(),
					pane[n.getY()][n.getX() - 1]);
			if (!isInCloseList(nChild_left)) {
				nChild_left.set(n, RIGHT);
				moveToOpenList(nChild_left);
				if (isChecked) {
					for (int i = 0; i < check.length; i++) {
						if (check[i][0] == 0 && check[i][1] == 0) {
							check[i][0] = nChild_left.pos[0];
							check[i][1] = nChild_left.pos[1];
							break;
						}
					}
				}
			}
		}
		if (hasChild(n, RIGHT) && n.father_dir != RIGHT) {
			Node nChild_right = new Node(n.getX() + 1, n.getY(),
					pane[n.getY()][n.getX() + 1]);
			if (!isInCloseList(nChild_right)) {
				nChild_right.set(n, LEFT);
				moveToOpenList(nChild_right);
				if (isChecked) {
					for (int i = 0; i < check.length; i++) {
						if (check[i][0] == 0 && check[i][1] == 0) {
							check[i][0] = nChild_right.pos[0];
							check[i][1] = nChild_right.pos[1];
							break;
						}
					}
				}
			}
		}
	}

	private void moveToCloseList(Node n) {
		closeList.addElement(n);
		openList.removeElementAt(nodeID);
	}

	private Node chooseLeastCostNode() {
		Node n = null;
		for (int i = 0; i < openList.size(); i++) {
			Node temp_n = (Node) openList.elementAt(i);
			if (n == null || n.F_value >= temp_n.F_value) {
				nodeID = i;
				n = temp_n;// 短路表达式原理
			}
		}
		return n;
	}

	private void continueSearch() {
		Node n = chooseLeastCostNode();
		if (n != null)
			search(n);
		else {
			isStoped = true;
			isFinded = false;
		}
	}

	private void search(Node n) {
		// n 是目标结点
		if (n.getX() == pos_end[0] && n.getY() == pos_end[1]) {
			isStoped = true;
			isFinded = true;
			path_node = n;
			return;
		}
		// n 是普通结点,添加n的子结点到待检查列表中，并计算各子结点的总代价,和深度值
		addChild(n);
		// n移去已检查列表
		moveToCloseList(n);
		// 继续处理待检查列表
		continueSearch();
	}

	class Node {
		private int pos[] = new int[2];// 节点位置

		byte father_dir = -1;// 父节点，-1没有，0上1下2左3右
		int value;// 代价 从地图数据中读出
		int G_value;// 从起始点到当前点的总的代价
		int F_value;// 当前点总代价
		int depth = 1;// 深度 从起点到当前结点的步数

		Node(int x, int y, int v) {
			pos[0] = x;
			pos[1] = y;
			value = v;
			G_value = value;
			F_value = getF(this);
		}

		Node(Node node) {
			pos[0] = node.pos[0];
			pos[1] = node.pos[1];
			father_dir = node.father_dir;
			value = node.value;
			G_value = node.G_value;
			F_value = node.F_value;
			depth = node.depth;
		}

		Node getFather() {
			switch (father_dir) {
			case UP:
				for (int i = 0; i < closeList.size(); i++) {
					Node node = (Node) closeList.elementAt(i);
					if (node.getX() == getX() && node.getY() == getY() - 1)
						return node;
				}
				break;
			case DOWN:
				for (int i = 0; i < closeList.size(); i++) {
					Node node = (Node) closeList.elementAt(i);
					if (node.getX() == getX() && node.getY() == getY() + 1)
						return node;
				}
				break;
			case LEFT:
				for (int i = 0; i < closeList.size(); i++) {
					Node node = (Node) closeList.elementAt(i);
					if (node.getX() == getX() - 1 && node.getY() == getY())
						return node;
				}
				break;
			case RIGHT:
				for (int i = 0; i < closeList.size(); i++) {
					Node node = (Node) closeList.elementAt(i);
					if (node.getX() == getX() + 1 && node.getY() == getY())
						return node;
				}
				break;
			}
			return null;
		}

		void set(Node father, byte Father_dir) {
			father_dir = Father_dir;
			depth += father.depth;
			G_value += father.G_value;
			F_value = getF(this);
		}

		int getX() {
			return pos[0];
		}

		int getY() {
			return pos[1];
		}
	}
}